//
// Created by Administrator on 2024/1/25.
//

#ifndef UNIONFIND_UNIONFIND1_H
#define UNIONFIND_UNIONFIND1_H

#include <iostream>
#include <cassert>

using namespace std;

namespace UF1 {
    class UnionFind{
    private:
        int* id;    // 一个数组
        int count;  // 数组容量
    public:
        UnionFind(int n) {
            count = n;
            id = new int[n];
            // 初始化，每个元素都是一个独立的组
            for(int i = 0; i < n; i++) {
                id[i] = i;
            }
        }
        ~UnionFind() {
            delete [] id;
        }
        // 查找：返回元素p的集合
        int find(int p) {
            assert(p >= 0 && p < count);
            return id[p];
        }
        // 是否连接.Quick Find
        bool isConnected(int p, int q) {
            return find(p) == find(q);
        }
        // 求两个元素p和q的连接起来的集合
        void unionElements(int p, int q) {
            int pID = find(p);
            int qID = find(q);

            if(pID == qID)
                return;

            for(int i = 0; i < count; i++)
                if(id[i] == pID)
                    id[i] = qID;
        }
    };
}

#endif //UNIONFIND_UNIONFIND1_H
